
/*
 * 
 * Problems No 5
 * Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
 * 解释： 如果一个字符串从左向右写和从右向左写是一样的,这样的字符串就叫做palindromic string.
 *       请找到一个字符串中最长的 palindromic string。
 *       如：  aaabaaaa  最长的 palindromic string 是 aaabaaa。
 * 
 * 思路：
 *   1 字符串反转之后，寻找最长的相同子串。(虽然实现了，但是说我超时。。。)
 *   
 *   2 从中间向两边查找左右对称的字符串，分奇数和偶数两次
 */
package com.leetcode.weicl.problems.no5;

import java.util.concurrent.TimeUnit;


/**
 * The Class Solution.<br>
 * 
 * @author FNST)WeiCL
 * @version 1.0
 */
public class Solution {
	int length = 0;
	int start = 0;
	int loop = 0;
	public String longestPalindrome(String s) {
//		String common = "";
		start = 0;
		length = 0;
		loop = 0;
		int strlen = s.length();
		int starti = strlen/2;
		int j = 0;
    	for (int i = 0; i < strlen; i++) {
    		if (length <= (strlen-i)*2) {
    			getHalfLength(s, starti + i);
    		}
//    		if (i == 0){
//    			continue;
//    		}
    		if (length <= (strlen+j)*2) {
    			getHalfLength(s, starti + j);
    			
    		}
    		j--;
        }
    	System.out.printf("start: %d, length: %d, loop: %d\n", start, length, loop);
    	
        return s.substring(start, start+length);
    }
	
	public int getHalfLength(String s, int k) {
		int halfLen = findPalinOdd(s, k);
		
		int nowLen = halfLen*2 +1;
		if (nowLen > length) {
			start = k - halfLen;
			length = nowLen;
		}
		
		halfLen = findPalinEven(s, k);
		nowLen = halfLen*2 +2;
		if (nowLen > length) {
			start = k - halfLen;
			length = nowLen;
		}
		
		return halfLen;
	}
	
	public int findPalinOdd(String s, int k) {
		int i;
		for (i = 1; k+i < s.length() && k-i>=0; i++) {
			loop++;
	        if (s.charAt(k+i) != s.charAt(k-i)) {
	        	break;
	        }
        }
		
		return i-1;
	}
	
	public int findPalinEven(String s, int k) {
		int i;
		for (i = 0; k+i+1 < s.length() && k-i>=0; i++) {
			loop++;
	        if (s.charAt(k+i+1) != s.charAt(k-i)) {
	        	break;
	        }
        }
		
		return i-1;
	}
	
    public String longestPalindrome2(String s) {
    	StringBuilder sb = new StringBuilder(s);
    	String rs = sb.reverse().toString();
    	
    	
        return maxCommonStr(s, rs);
    }

	/**
	 * 最长的相同子串
	 * @param s
	 * @param rs
	 * @return
	 */
    private String maxCommonStr(String s, String rs) {
	    if (s.equals(rs)) {
	    	return s;
	    }
	    
	    int length = s.length();
	    String common = "";
    	
	    int start = 0;
	    int end = 0;
	    for (int i = 0; i < length; i++) {
	    	if (common.length() > length-i) {
	    		break;
	    	}
	    	start = i;
	    	int max = length-i;
	        for (int j = 0; j < max; j++) {
	        	end = start;
	        	
	        	for (int m = j; m < length; m++) {
	                
		            if (end < length && s.charAt(end) == rs.charAt(m)) {
		            	end++;
//		            	System.out.printf("same at:%d, %d, %d \n", end, start, j);
		            } else {
//		            	System.out.printf("not same at:%d, %d, %d \n", end, start, j);
		            	if (end - start > common.length()) {
		            		common = s.substring(start, end);
		            		System.out.println("str: " + common);
		            		i = end-1;
		            	}
		            	break;
		            }
                }
	        	if (end - start > common.length()) {
	        		common = s.substring(start, end);
	        		System.out.println("str2: " + common);
	        		i = end-1;
	        	}
            }
	        
	        
        }
	    
	    return common;
    }
    
    static long startTime = 0;
    public static void start() {
    	startTime = System.nanoTime();
    }
    public static void end() {
    	System.out.println("time: " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime()- startTime) + " ms\n");
    }
    
    public static void main(String[] args) {
	    Solution sol = new Solution();
	    
	    start();
	    System.out.println(sol.longestPalindrome("bb"));
	    end();
	    
	    start();
	    System.out.println(sol.longestPalindrome("a"));
	    end();
	    
	    start();
	    System.out.println(sol.longestPalindrome("qqq"));
	    end();
	    
	    start();
	    System.out.println(sol.longestPalindrome("bcc"));
	    end();
	    
	    start();
	    System.out.println(sol.longestPalindrome("aaabaaaa"));
	    end();
	    /*
	     * civilwartesting
	     * gnitsetrawlivic
	     */
	    start();
	    System.out.println(sol.longestPalindrome("civilwartesting"));
	    end();
	    
	    start();
	    System.out.println(sol.longestPalindrome("civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"));
	    end();
	    
	    start();
	    System.out.println(sol.longestPalindrome("jrjnbctoqgzimtoklkxcknwmhiztomaofwwzjnhrijwkgmwwuazcowskjhitejnvtblqyepxispasrgvgzqlvrmvhxusiqqzzibcyhpnruhrgbzsmlsuacwptmzxuewnjzmwxbdzqyvsjzxiecsnkdibudtvthzlizralpaowsbakzconeuwwpsqynaxqmgngzpovauxsqgypinywwtmekzhhlzaeatbzryreuttgwfqmmpeywtvpssznkwhzuqewuqtfuflttjcxrhwexvtxjihunpywerkktbvlsyomkxuwrqqmbmzjbfytdddnkasmdyukawrzrnhdmaefzltddipcrhuchvdcoegamlfifzistnplqabtazunlelslicrkuuhosoyduhootlwsbtxautewkvnvlbtixkmxhngidxecehslqjpcdrtlqswmyghmwlttjecvbueswsixoxmymcepbmuwtzanmvujmalyghzkvtoxynyusbpzpolaplsgrunpfgdbbtvtkahqmmlbxzcfznvhxsiytlsxmmtqiudyjlnbkzvtbqdsknsrknsykqzucevgmmcoanilsyyklpbxqosoquolvytefhvozwtwcrmbnyijbammlzrgalrymyfpysbqpjwzirsfknnyseiujadovngogvptphuyzkrwgjqwdhtvgxnmxuheofplizpxijfytfabx"));
	    end();
	    
	    start();
	    System.out.println(sol.longestPalindrome("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
	    end();
	    
	    
	    /*
	     * aaabcaaaa
	     * aaaacbaaa
	     */
//	    start = System.currentTimeMillis();
//	    System.out.println(sol.longestPalindrome("aaabcaaaa"));
//	    System.out.println("time: " + (System.currentTimeMillis()- start) + " ms\n");
    }
}
